﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Task7
{
    public class Graph
    {
        int[,] nodes;
        bool[] visited;
        int[] currentStepsLength;
        int[] currentPath;

        public Graph(int[,] nodes)
        {
            this.nodes = nodes;
            this.visited = new bool[nodes.GetLength(0)];
            this.currentStepsLength = new int[nodes.GetLength(0)];
            for (int i = 0; i < currentStepsLength.GetLength(0); i++)
            {
                currentStepsLength[i] = int.MaxValue;
            }

            currentPath = new int[nodes.GetLength(0)];
        }

        private int GetPreviousNode(int currentNode)
        {
            return currentPath[currentNode];
        }

        public Stack<int> GetPath(int start, int end)
        {
            FindShortestPath(start, end);
            Stack<int> path = new Stack<int>();

            int current = end;

            do
            {
                path.Push(current);
                current = GetPreviousNode(current);
            } while (current != start);

            path.Push(current);


            return path;
        }

        private void FindShortestPath(int start, int end)
        {
            Dictionary<int, int> notVisited = new Dictionary<int, int>();
            for (int i = 0; i < visited.GetLength(0); i++)
            {
                notVisited.Add(i, i);
            }

            int currentNode = start;

            while (notVisited.Count > 0)
            {
                List<int> connectedNodes = GetConnectedNodes(currentNode);

                foreach (int node in connectedNodes)
                {
                    if (!visited[node])
                    {
                        if (currentStepsLength[currentNode] < int.MaxValue)
                        {
                            int newLength = currentStepsLength[currentNode] + nodes[currentNode, node];
                            if (newLength < currentStepsLength[node])
                            {
                                currentStepsLength[node] = currentStepsLength[currentNode] + nodes[currentNode, node];
                                currentPath[node] = currentNode;
                            }
                        }
                        else
                        {
                            currentStepsLength[node] = nodes[currentNode, node];
                            currentPath[node] = currentNode;
                        }
                    }
                }

                visited[currentNode] = true;
                if (currentNode == end)
                {
                    return;
                }
                notVisited.Remove(currentNode);

                int currentMinValue = int.MaxValue;
                int currentMinIndex = -1;

                for (int i = 0; i < currentStepsLength.GetLength(0); i++)
                {
                    if (! visited[i] && currentMinValue > currentStepsLength[i])
                    {
                        currentMinValue = currentStepsLength[i];
                        currentMinIndex = i;
                    }
                }

                if (currentMinValue == int.MaxValue)
                {
                    return;
                }

                currentNode = currentMinIndex;
            }
        }

        private List<int> GetConnectedNodes(int node)
        {
            List<int> lst = new List<int>();
            for (int i = 0; i < nodes.GetLength(0); i++)
            {
                if (nodes[node, i] < int.MaxValue)
                {
                    lst.Add(i);
                }
            }

            return lst;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            int[,] nodes = new int[,]
            {
                { int.MaxValue, 23,  int.MaxValue, int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue,  8, int.MaxValue,  int.MaxValue },
	            { int.MaxValue,  int.MaxValue,  int.MaxValue, 3,  int.MaxValue,  int.MaxValue, 34,  int.MaxValue, int.MaxValue,  int.MaxValue },
	            { int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue, 25, int.MaxValue,  int.MaxValue },
	            { int.MaxValue,  int.MaxValue,  6, int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue,  int.MaxValue },
	            { int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue,  int.MaxValue, 10,  int.MaxValue,  int.MaxValue, int.MaxValue,  int.MaxValue },
	            { int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue, 12,  int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue,  int.MaxValue },
	            { int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue,  int.MaxValue },
	            { int.MaxValue,  int.MaxValue, 25, int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue, 30 },
	            { int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue,  int.MaxValue },
	            { int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue,  int.MaxValue, int.MaxValue,  int.MaxValue }

            };

            Graph g = new Graph(nodes);
            Stack<int> path = g.GetPath(0, 2);

            while (path.Count > 0)
            {
                Console.WriteLine(path.Pop());
            }
        }
    }
}
